Given the continually increased reliance on computers in contemporary society, computer technology has had to advance on many fronts to keep up with increased demand. One particular subject of significant research and development efforts is parallelism, i.e., the performance of multiple tasks in parallel.
A number of computer software and hardware technologies have been developed to facilitate increased parallel processing. From a software standpoint, multithreaded operating systems and kernels have been developed, which permit computer programs to concurrently execute in multiple “threads” so that multiple tasks can essentially be performed at the same time. Threads generally represent independent paths of execution for a program. For example, for an e-commerce computer application, different threads might be assigned to different customers so that each customer's specific e-commerce transaction is handled in a separate thread.
From a hardware standpoint, computers increasingly rely on multiple microprocessors to provide increased workload capacity. Furthermore, some microprocessors have been developed that support the ability to execute multiple threads in parallel, effectively providing many of the same performance gains attainable through the use of multiple microprocessors.
From a software standpoint, some computers implement the concept of logical partitioning, where a single physical computer is permitted to operate essentially like multiple and independent “virtual” computers (referred to as logical partitions), with the various resources in the physical computer (e.g., processors, memory, input/output devices) allocated among the various logical partitions. Each logical partition executes a separate operating system, and from the perspective of users and of the software applications executing on the logical partition, operates as a fully independent computer.
With logical partitioning, a shared resource, often referred to as a “hypervisor” or partition manager, manages the logical partitions and facilitates the allocation of resources to different logical partitions. For example, a partition manager may allocate resources such as processors, workstation adapters, storage devices, memory space, network adapters, etc. to various partitions to support the relatively independent operation of each logical partition in much the same manner as a separate physical computer.
In connection with managing logical partitions, it may be desirable for individual partitions to be created and deleted without requiring the entire computer to be shut down and restarted, thus ensuring the continuing availability of other partitions in the computer. Creating new partitions is typically not particularly problematic, as new data structures may be created to support a new partition without risk of conflict. Deleting partitions, on the other hand, is often more problematic due to the need to ensure that existing data structures for a partition are no longer in use when they are deallocated, or removed, from the computer.
In particular, deleting any data structure that is capable of being accessed by multiple threads in a multithreaded computer environment requires care to be taken to ensure that no thread is still using a data structure before it is deleted. Otherwise, a thread may attempt to later access the data structure after it has been deleted, resulting in indeterminate results and potential system failure.
Conventionally, accesses to many shared data structures are managed through the use of semaphores, or spin locks. A semaphore is typically implemented as a variable or token that is associated with a shared pointer to a data structure, and that is readable by multiple threads to determine whether the pointer is currently being used by one of the threads. Whenever a thread reads a semaphore that indicates that no other thread is currently using the pointer, the thread is able to set the semaphore to a value that indicates to all other threads that the pointer is currently in use (a process referred to as “acquiring” a semaphore). Thus, when another thread wishes to access the data structure, but detects that the semaphore is held by another thread, that thread is required to wait until the other thread releases the semaphore to indicate that the pointer (and thus the data structure) is again accessible to other threads. As such, only one thread is permitted to hold a semaphore at any given time.
A significant drawback to a semaphore or spin lock is the substantial processing overhead associated with checking and acquiring a semaphore whenever an associated data structure needs to be accessed. For example, in the case of a logically-partitioned computer, a number of data structures are accessed frequently during the normal course of operation. Partition control blocks, for example, which are used to store critical partition configuration information, are typically accessed during practically every partition management operation. Requiring a thread to acquire a semaphore each time a partition control block needs to be accessed has been found to be prohibitively expensive from a performance standpoint.
Therefore, a substantial need has arisen for a manner of supporting the deallocation of data structures in a multithreaded computer with reduced processing overhead.